Perfect squares [Hash]

Time: O(NxSqrt(N)); Space: O(N); medium

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12

Output: 3

Explanation:

  • 12 = 4 + 4 + 4

Example 2:

Input: n = 13

Output: 2

Explanation:

  • 13 = 4 + 9

[1]:

class Solution1(object):
    """
    Time: O(N*SQRT(N))
    Space: O(N)
    """
    _num = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        num = self._num
        while len(num) <= n:
            num += min(num[-i*i] for i in range(1, int(len(num)**0.5+1))) + 1,
        return num[n]



[2]:

s = Solution1()

n = 12
assert s.numSquares(n) == 3

n = 13
assert s.numSquares(n) == 2